"""
Given an integer array A, and an integer target, return the number of tuples i, j, k  such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.



Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation:
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.
Example 2:

Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation:
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.


Note:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300
"""

import collections

def threeSumMulti(A,target):
    MOD = 10 ** 9 + 7   # 题目要求除得余数
    count = collections.Counter(A)
    keys = sorted(count)    # 把字典中的key排序打印出来
    res = 0
    # 三个数值分别为A[I],A[J],A[k]
    for i, x in enumerate(keys): # enumerate能变成索引和值对应起来的东西，如果是四位数字之和就需要两层循环
        T = target - x  # 第一个数值
        j, k = i, len(keys) - 1
        while j <= k:   # 可以相等
            y, z = keys[j], keys[k]
            if y + z < T:
                j = j + 1
            elif y + z > T:
                k = k - 1
            else:    # 三数和为target，这时候需要统计各种情况
                if i < j < k:
                    res = res + count[x] * count[y] * count[z]
                elif i == j < k:
                    res = res + count[x] * (count[x] - 1) * count[z] / 2
                elif i < j == k:
                    res = res + count[x] * count[y] * (count[y] - 1) / 2
                else:
                    res = res + count[x] * (count[x] - 1) * (count[x] - 2) / 6
                k = k - 1
                j = j + 1
    return int(res) % MOD



if __name__ == '__main__':
    # print(threeSumMulti([1, 1, 2, 2, 3, 4, 3, 4, 5, 5, 5], 8))
    print(threeSumMulti([0, 0, 0, 0, 0, 0], 0))